package com.algorithm.liyc.combine;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * 0491.递增子序列
 *
 * 给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
 *
 * 说明:
 * ● 给定数组的长度不会超过15。
 * ● 数组中的整数范围是 [-100,100]。
 * ● 给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。
 *
 * @author Liyc
 * @date 2024/1/23 14:14
 **/

public class Solution10 {
    private List<List<Integer>> result = new ArrayList<>();
    private LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> findSubsequences1(int[] nums) {
        findSubsequences2(nums, 0);
        return result;
    }

    public void findSubsequences2(int[] nums, int startIndex) {
        if (path.size() > 1) {
            result.add(new ArrayList<>(path));
            // 注意这里不要加return，要取树上的节点
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = startIndex; i < nums.length; i++) {
            if (!path.isEmpty() && nums[i] < path.getLast()) {
                continue;
            }
            // 使用过了当前数字
            if (map.getOrDefault(nums[i], 0) >= 1) {
                continue;
            }
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
            path.add(nums[i]);
            findSubsequences2(nums, i+1);
            path.removeLast();
        }
    }
}
